package myself.a013Map;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author 叶之越
 * Description
 * Date 2021/2/1
 * Time 14:58
 * Mail 739153436@qq.com
 */
public class Dijkstra {
    public static Map<Node, Integer> dijkstra1(Node from) {
        // 创建我们的Map距离表
        Map<Node, Integer> distanceMap = new HashMap<>();
        // 创建OK表
        Set<Node> set = new HashSet<>();
        // 基础元素存入，距离目标节点最短路径的节点
        distanceMap.put(from, 0);
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, set);
        while (minNode != null) {
            Integer distance = distanceMap.get(minNode);
            for (Edge edge : minNode.edges) {
                int weigth = edge.weigth;
                Node next = edge.to;
                if (!set.contains(next)) {
                    distanceMap.put(next, weigth + distance);
                } else {
                    distanceMap.put(next, Math.min(distanceMap.get(next), weigth + distance));
                }
            }
            set.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, set);
        }
        return distanceMap;
    }

    public static Node getMinDistanceAndUnselectedNode(Map<Node, Integer> distanceMap, Set<Node> touchedNodes) {
        Node minNode = null;
        Integer minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            if (!touchedNodes.contains(node) && entry.getValue() <= minDistance) {
                minNode = node;
                minDistance = entry.getValue();
            }
        }
        return minNode;
    }
}
